package 二叉树;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

public class JZ34二叉树中和为某一值的路径 {

    /**
     * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。
     * 从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
     *
     * 示例:
     * 给定如下二叉树，以及目标和 target = 22，
     *
     *               5
     *              / \
     *             4   8
     *            /   / \
     *           11  13  4
     *          /  \    / \
     *         7    2  5   1
     * 返回:
     * [
     *    [5,4,11,2],
     *    [5,8,4,5]
     * ]
     *  
     * 提示：
     * 节点总数 <= 10000
     * 注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/
     */

    private List<List<Integer>> result=new ArrayList<>();
    private int target;

    public List<List<Integer>> pathSum(TreeNode root, int target) {

        if(root==null){
            return result;
        }

        this.target=target;
        dfs(root,new ArrayList<>(),0);
        return result;
    }

    private void dfs(TreeNode node,List<Integer> path,int sum) {

        if(node==null){
            return;
        }

        path.add(node.val);
        sum+=node.val;

        if(sum==target&&node.left==null&&node.right==null){
            result.add(new ArrayList<>(path));
            path.remove(path.size()-1);
            return;
        }

        dfs(node.left,path,sum);
        if(node.right==null){
            path.remove(path.size()-1);
            return;
        }
        dfs(node.right,path,sum);

        path.remove(path.size()-1);
        sum-=node.val;
    }

    public static void main(String[] args) {
        JZ34二叉树中和为某一值的路径 jz=new JZ34二叉树中和为某一值的路径();
        /**
         * [1]
         * 0
         * 输出：
         * [[]]
         * 预期结果：
         * []
         */
        TreeNode treeNode =
                TreeNode.getNodeByArr(new Integer[]{5,4,8,11,null,13,4,7,2,null,null,5,1});
        treeNode.printNode();
        List<List<Integer>> result = jz.pathSum(treeNode, 22);
        System.out.println(JSON.toJSONString(result));
    }

}
